/**
 * @ClassName KP22_bitMap3
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/16 18:39
 */

import java.util.HashSet;

/**
 * 从任意数字开始存储
 * 位图 用 & >> 来实现位图数字的存储，效率较慢
 * 暂且考虑存储的数字为正数
 */
public class KP22_bitMap3 {
    public static class BitMap {
        private long[] bits;
        private int max;
        private int start;
        private int size;

        public int getMax() {
            return max;
        }

        public int getStart() {
            return start;
        }

        /**
         * 存储范围：0 ~ max + 1
         *
         * @param max
         */
        public BitMap(int max) {
            this.start = 0;
            this.max = max;
            // 根据最大值生成数组的个数（多少个数组空间能包含0-max的数）
            bits = new long[(max + 64) >> 6];
            this.size = bits.length;
        }

        /**
         * 存储范围：n ~ max - n + 1
         * start 起始点
         *
         * @param max
         */
        public BitMap(int max, int start) {
            this.start = start;
            this.max = max;
            // 根据最大值生成数组的个数（多少个数组空间能包含0-max的数）
            bits = new long[((max - start) + 64) >> 6];
            this.size = bits.length;
        }

        public void offer(int num) {
            // (num - this.start) >> 6 表示数num存放的数组空间位置
            // 1L << ((num - this.start) & 63) 表示num在这个64位bit空间的第几位信息
            // start也在位图中，所以不+1
            bits[(num - this.start) >> 6] |= (1L << ((num - this.start) & 63));
        }

        public void remove(int num) {
            // (num - this.start) >> 6 表示数num存放的数组空间位置
            // 1L << ((num - this.start) & 63) 表示num在这个64位bit空间的第几位信息
            bits[(num - this.start) >> 6] &= ~(1L << ((num - this.start) & 63));
        }

        public boolean isContains(int num) {
            // (num - this.start) >> 6 表示数num存放的数组空间位置
            // 1L << ((num - this.start) & 63) 表示num在这个64位bit空间的第几位信息
            return (bits[(num - this.start) >> 6] & (1L << ((num - this.start) & 63))) != 0;
        }

        // point表示第几位信息，从0位开始
        public int printNum(int col, int point) {
            return col * 64 + point + start;
        }
    }

    public static void testBitMap() {
        BitMap bitMap = new BitMap(27, -100);
        for (int i = 0; i < bitMap.size; i++) {
            for (int j = 0; j <= 63; j++) {
                int num = bitMap.printNum(i, j);
                if (num <= bitMap.getMax()) {
                    System.out.print(num + " ");
                }
            }
            System.out.println();
        }
    }

    /*public static void testBitMap() {
        double start = System.currentTimeMillis();
        System.out.println("测试开始！");
        int max = 10000;
        int testTimes = 100000000;
        KP22_bitMap1.BitMap bitMap = new KP22_bitMap1.BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTimes; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.33) {
                bitMap.offer(num);
                set.add(num);
            } else if (decide < 0.66) {
                bitMap.remove(num);
                set.remove(num);
            } else {
                if (bitMap.isContains(num) != set.contains(num)) {
                    System.out.println("error1 num:" + num);
                    break;
                }
            }
        }
        for (int i = 0; i < max; i++) {
            if (bitMap.isContains(i) != set.contains(i)) {
                System.out.println("error" + i);
            }
        }
        double end = System.currentTimeMillis();
        System.out.println("测试结束！");
        System.out.println("消耗时间：" + (end - start));
    }*/

    public static void main(String[] args) {
        testBitMap();
    }
}
